package NowCoder.JavaSE.Array;
import java.util.*;
/**
 * QQ2 微信红包简单  通过率：26.92%  时间限制：3秒  空间限制：32M
 * 知识点
 * 模拟
 * 描述
 * 春节期间小明使用微信收到很多个红包，非常开心。在查看领取红包记录时发现，某个红包金额出现的次数超过了红包总数的一半。
 * 请帮小明找到该红包金额。写出具体算法思路和代码实现，要求算法尽可能高效。
 *
 * 给定一个红包的金额数组 gifts 及它的大小 n ，请返回所求红包的金额。
 *
 * 若没有金额超过总数的一半，返回0。
 *
 * 数据范围：1≤n≤1000  ,红包金额满足 1 ≤ gift_i ≤100000
 * 示例1
 * 输入：
 * [1,2,3,2,2],5
 * 返回值：
 * 2
 * 示例2
 * 输入：
 * [1,1,2,2,3,3],6
 * 返回值：
 * 0
 * https://www.nowcoder.com/practice/fbcf95ed620f42a88be24eb2cd57ec54?tpId=167&tqId=34050&ru=/exam/oj
 */
public class 微信红包_QQ2 {
    //排序以后，中位数一定是众数
//    public static int getValue(int[] gifts, int n) {
//        // write code here
//        Arrays.sort(gifts);
//        //取中位数，查找该数的出现次数
//        int num = gifts[n / 2];
//        int number = 0;
//        for(int i : gifts){
//            if(i == num){
//                number++;
//            }
//        }
//        if(number > (n / 2)){
//            return num;
//        }
//        return 0;
//    }

    //摩尔投票法
    public static int getValue(int[] gifts, int n) {
        // write code here
        int y = 0;//y代表是众数
        int sum = 0;
        for(int i : gifts){
            if(sum == 0){
                y = i;
                sum++;
            }
            else if(i != y){
                sum--;
            }else{
                sum++;
            }
        }

        int num = 0;
        for(int i : gifts){
            if(y == i){
                num++;
            }
        }

        if(num > n / 2){
            return y;
        }else{
            return 0;
        }
    }


    //分治法
    public static  int recurtion(int[] nums, int begin, int end){
        if( begin == end ) //基本情况
            return nums[begin];

        int mid = (begin+end)/2; //分治
        int left = recurtion(nums, begin, mid);
        int right = recurtion(nums, mid+1, end);

        if( left == right )
            return left;

        int leftCount = 0, rightCount = 0;
        for(int i=begin; i<=end; i++) //寻找每个子集中次数最多的元素
            if( nums[i] == left )
                leftCount++;
            else if( nums[i] == right )
                rightCount++;

        if( leftCount > rightCount )
            return left;
        return right;
    }

    public static void main(String[] args) {
        int[] arr = {975,975,975,975,975,975,975,975,975,975,975,975,975,975,975,975,975,975,
                        975,975,975,975,975,975,1336,1327,709,3159,5680,7573,5914,8067,6624,7745,9334,
                        3502,9200,7158,606,1705,5157,5405,1148,6999,9405};
        int n = 45;
        System.out.println(recurtion(arr, 0, 44));
        System.out.println(getValue(arr, n));
    }
}
